package com.ai.zuochengyun.phase01.class04;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 输入正整数组costs、正整数组profits，正数k、正数m，输出你最后获得的最大money
 */
public class Code04_IPO {

    public static void main(String[] args) {
        Invest[] invests = new Invest[4];
        invests[0] = new Invest(5, 1);
        invests[1] = new Invest(1, 3);
        invests[2] = new Invest(2, 5);
        invests[3] = new Invest(6, 4);
        int maxMoney2 = getMaxMoney2(invests, 3, 1);
        System.out.println(maxMoney2);
    }

    private static int getMaxMoney2(Invest[] invests, int k, int m) {
        if (invests == null || invests.length == 0) {
            return m;
        }
        PriorityQueue<Invest> costs = new PriorityQueue<>(new CostComparator());
        for (Invest invest : invests) {
            costs.offer(invest);
        }

        PriorityQueue<Invest> profits = new PriorityQueue<>(new ProfitComparator());
        for (int i = 0; i < k; i++) {
            // 将能负担得起的放入大根堆中
            // costs.peek().cost 如果大于 m，就不进入循环，如果将这个逻辑判断放入内部，小心死循环
//            while (!costs.isEmpty()) {
//                if (costs.peek().cost > m) {
//                    break;
//                }
//                profits.add(costs.poll());
//            }
            while (!costs.isEmpty() && costs.peek().cost <= m) {
                profits.add(costs.poll());
            }
            // 如果做不够k轮，需要提前结束
            if (profits.isEmpty()) {
                return m;
            }
            // 取盈利最大的
            m += profits.poll().profit;
        }
        return m;
    }

    /**
     * 按花费升序排序
     */
    private static class CostComparator implements Comparator<Invest> {

        @Override
        public int compare(Invest o1, Invest o2) {
            return o1.cost - o2.cost;
        }
    }

    /**
     * 按利润降序排序
     */
    private static class ProfitComparator implements Comparator<Invest> {

        @Override
        public int compare(Invest o1, Invest o2) {
            return o2.profit - o1.profit;
        }
    }

    private static class Invest {
        public int cost;

        public int profit;

        public Invest(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }
}
